/************************************************************
 * Project Name		[Thinking_In_Java]
 * File Name     	[pkg_algorithm.Joseph.java]
 * Creation Date 	[15-Jun-2014]
 * 
 * Copyright© ge.y.yang@gmail.com All Rights Reserved
 * 
 * Work hard, play harder, think big and keep fit
 ************************************************************/
package pkg_algorithm;

/**
 * 约瑟夫问题
 * 
 * @author 不落的太阳(Sean Yang)
 * @version 1.0
 * @since JDK 6
 * 
 */
public class Joseph {

	/**
	 * 首先判断数组里面的元素是否为true, 即人员是否在圈中.<br>
	 * 如果为true则继续计数, 计数器累加 当计数器到达3的时候, <br>
	 * 首先计数器要归零,<br>
	 * 然后boolean数组中该位置的元素要置为false, 同时总数减少一个,<br>
	 * 索引下标增加一个<br>
	 * 由于多人首尾相连, 所以当到达最后一个元素的时候, 索引要归零
	 * 
	 * @param array
	 *            要检测的数组
	 */
	public static void joseph(boolean[] array) {
		for (int i = 0; i < array.length; i++) {
			array[i] = true;
		}

		int counter = 0;// 计数器
		int leftCount = array.length;// 剩余人数
		int index = 0;// 索引

		while (leftCount > 1) {
			if (array[index]) {
				counter++;
				if (counter == 3) {
					counter = 0;
					array[index] = false;
					leftCount--;
				}
			}
			index++;
			if (index == array.length) {
				index = 0;
			}
		}

		for (int i = 0; i < array.length; i++) {
			if (array[i]) {
				System.out.println("剩余人员的位置是" + (i + 1));
			}
		}
	}

	/**
	 * 测试方法
	 * 
	 * @param args
	 *            命令行参数
	 */
	public static void main(String[] args) {
		boolean[] array = new boolean[500];
		Joseph.joseph(array);
	}
}
